package com.zk.algorithm.bit;

import com.zk.algorithm.Utils;
import com.zk.algorithm.annotation.JianZhiOffer;

/**
 * 一个数字出现一次，其它都是出现3次
 *
 * 思路：如果一个数字出现 3 次，那么它的二进制位表示的每一位 (0 或者 1) 也出现 3 次。
 * 如果把所有出现 3 次的数字的二进制表示的每一位都分别加起来，那么每一位的和都能被 3 整除。
 */
@JianZhiOffer
public class SingleNumber2 {

    public static void main(String...args) {
        Utils.println(new SingleNumber2().findSingleNumber(new int[] {
                1,1,1,2,2,2,3,4,5,3,5,3,5
        }));
    }

    public int findSingleNumber(int[] numbers) {
        // 4 byte
        int[] bitSum = new int[32];

        for (int i = 0; i < numbers.length; i++) {
            int bitMask = 1;
            for (int j = 31; j >= 0; j--) {
                int bit = numbers[i] & bitMask;
                if (bit != 0) {
                    bitSum[j] += 1;
                }

                bitMask = bitMask << 1;
            }
        }

        int result = 0;
        for (int i = 0; i < 32; i++) {
            result = result << 1;
            result += bitSum[i] % 3;
        }

        return result;
    }

}
